{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Семинар 6. Контейнеры и итераторы."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br />"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### begin && end"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "`begin()`, `end()` - методы у контейнеров, возвращающие итераторы:\n",
    "* `begin()` на первый элемент в контейнере\n",
    "* `end()` на следующий за последним элементом"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Как, зная `begin()` и `end()`, проверить, что контейнер пуст?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```c++\n",
    "std::vector<int> v = {10, 20, 30, 40};\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![](vector_internals.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```c++\n",
    "auto it = v.begin();\n",
    "std::cout << *it; // 10\n",
    "        \n",
    "++it;\n",
    "std::cout << *it; // 20\n",
    "        \n",
    "++it;\n",
    "std::cout << *it; // 30\n",
    "\n",
    "++it;\n",
    "std::cout << *it; // 40\n",
    "\n",
    "++it; // it == v.end()\n",
    "std::cout << *it; // UB - you should never dereference end()!\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br />"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### Итераторы и ассоциативные контейнеры"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Обратить внимание на сложности итерирования по ассоциативным контейнерам"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![](unordered_internals.jpg)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br />"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### range for"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "https://en.cppreference.com/w/cpp/language/range-for"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```c++\n",
    "std::vector<int> v = {10, 20, 30, 40};\n",
    "for (int x : v)\n",
    "    std::cout << x; // во что разворачивается range-for? (упрощённо)\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "во что разворачивается range-for? (упрощённо)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```c++\n",
    "for (auto x : v) { ... }\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```c++\n",
    "{\n",
    "    auto&& __range = v;\n",
    "    auto __begin = __range.begin();\n",
    "    auto __end = __range.end();\n",
    "    for (; __begin != __end; ++__begin) {\n",
    "        auto x = *__begin;\n",
    "        ...\n",
    "    }\n",
    "}\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Смысл в том, что как только для пользовательского контейнера определены итераторы и методы `begin()`, `end()`, `cbegin()`, `cend()`, для него \"из коробки\" начинает работать range-for."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br />"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### Инвалидация итераторов"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Итераторы могут быть инвалидированы, если контейнер меняется.\n",
    "\n",
    "Рассмотрим пример `std::vector` в предположении, что итератор - указатель на элемент в `std::vector`.\n",
    "\n",
    "(нарисовать происходящее на доске)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```c++\n",
    "std::vector<int> v = {10, 20, 30, 40};\n",
    "\n",
    "auto v_end = v.end();\n",
    "auto it = v.begin();\n",
    "\n",
    "v.push_back(50);\n",
    "// at this point:\n",
    "// |it|    - invalidated\n",
    "// |v_end| - invalidated\n",
    "\n",
    "std::cout << *it; // oooops, ub\n",
    "if (v.begin() == v_end)  // ooooops, ub\n",
    "    ...;\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "https://en.cppreference.com/w/cpp/container/vector/push_back"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```c++\n",
    "std::set<int> s = {20, 30, 40, 50};\n",
    "        \n",
    "auto it = s.begin();\n",
    "std::cout << *it;  // 20\n",
    "\n",
    "s.insert(10);\n",
    "\n",
    "std::cout << *it;  // ok, 20\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Почему так? Потому что документация:\n",
    "\n",
    "https://en.cppreference.com/w/cpp/container/set/insert"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*У каждого контейнера у каждого метода прописан контракт на валидность итераторов (когда и какие итераторы инвалидируются).*\n",
    "\n",
    "*Читайте документацию внимательно!*"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br />"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### Правильное удаление элементов из map/set/vector/... по условию"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Как неправильно удалять элементы из `std::set`:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```c++\n",
    "std::set<int> s = {1, 2, 3, 4, 5};\n",
    "\n",
    "auto it = s.begin();\n",
    "for(; it != s.end(); ++it)\n",
    "    if((*it) % 2 == 1)\n",
    "        s.erase(it);\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "В каком месте баг?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Правильное удаление:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```c++\n",
    "std::set<int> s = {1, 2, 3, 4, 5};\n",
    "for(auto it = s.begin(); it != s.end();)\n",
    "{\n",
    "    if((*it) % 2 == 1)\n",
    "        it = s.erase(it);\n",
    "    else\n",
    "        ++it;\n",
    "}\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br />"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### Операции над итераторами доступа"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```c++\n",
    "std::vector<int> v = {10, 20, 30, 40, 50};\n",
    "        \n",
    "auto it = v.begin();\n",
    "\n",
    "// некоторые итераторы позволяют брать следующий элемент:\n",
    "auto jt_1 = it + 1;\n",
    "auto jt_2 = std::next(it);\n",
    "        \n",
    "// некоторые итераторы позволяют брать предыдущий элемент:\n",
    "auto jt_3 = it - 1;         // ?\n",
    "auto jt_4 = std::prev(it);  // ?\n",
    "        \n",
    "// некоторые итераторы позволяют прыгать на n элементов вперёд:\n",
    "auto jt_5 = it + 4;\n",
    "auto jt_6 = std::advance(it, 4);\n",
    "\n",
    "// некоторые итераторы позволяют прыгать на n элементов назад:\n",
    "auto jt_7 = it - 4;                // ?\n",
    "auto jt_8 = std::advance(it, -4);  // ?\n",
    "\n",
    "// некоторые итераторы позволяют считать расстояние между ними:\n",
    "std::cout << std::distance(it, jt_5);  // 4\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Стандартные операции над итераторами доступа (access iterators):\n",
    "* `std::next`\n",
    "* `std::prev`\n",
    "* `std::advance`\n",
    "* `std::distance`"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br />"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### Типы итераторов"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Как вы помните, у access iterators у `std::forward_list` нельзя делать `--it`, они только для хождения вперёд и только по одному шагу. А у `std::vector` можно вперёд-назад и на любое число шагов за раз. По этому принципу классифицируются итераторы доступа:\n",
    "* [Forward Iterator](https://en.cppreference.com/w/cpp/named_req/ForwardIterator)\n",
    "* [Bidirectional Iterator](https://en.cppreference.com/w/cpp/named_req/BidirectionalIterator)\n",
    "* [Random Access Iterator](https://en.cppreference.com/w/cpp/named_req/RandomAccessIterator)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Классификация имеет важное значение для алгоритмов. Например, алгоритм сортировки работает только с Random Access Iterator:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```c++\n",
    "std::vector<int> v = {20, 30, 10};\n",
    "std::sort(v.begin(), v.end());  // ok\n",
    "        \n",
    "std::list<int> l = {20, 30, 10};\n",
    "std::sort(l.begin(), l.end());  // compile-time error\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "И это отражено в требованиях к алгоритму:\n",
    "    \n",
    "https://en.cppreference.com/w/cpp/algorithm/sort"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Поэтому для `std::list` реализовали свой `sort`:\n",
    "\n",
    "https://en.cppreference.com/w/cpp/container/list/sort"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```c++\n",
    "std::list<int> l = {20, 30, 10};\n",
    "l.sort();\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br />"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Прочие типы итераторов:\n",
    "* [Input Iterator](https://en.cppreference.com/w/cpp/named_req/InputIterator)\n",
    "* [Output Iterator](https://en.cppreference.com/w/cpp/named_req/OutputIterator)\n",
    "* [Reverse Iterator](https://en.cppreference.com/w/cpp/iterator/reverse_iterator)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Мощь и безобразие итераторов в двух примерах:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```c++\n",
    "std::istringstream str(\"0.1 0.2 0.3 0.4\");\n",
    "const double sum = std::accumulate(std::istream_iterator<double>(str),\n",
    "                                   std::istream_iterator<double>(),\n",
    "                                   0.);\n",
    "\n",
    "\n",
    "std::vector<int> v = {1, 2, 3, 4, 5};\n",
    "std::copy(v.begin(),\n",
    "          v.end(),\n",
    "          std::ostream_iterator<int>(std::cout, \" \"));\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br />"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### reverse_iterator"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![](reverse_iterator.jpg)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```c++\n",
    "std::vector<int> v = {10, 20, 30, 40};\n",
    "\n",
    "// обход в прямом направлении в стиле до С++11\n",
    "std::copy(v.begin(),\n",
    "          v.end(),\n",
    "          std::ostream_iterator<int>(std::cout, \" \")); // 10 20 30 40\n",
    "            \n",
    "// обход в обратном направлении:\n",
    "std::copy(v.rbegin(),\n",
    "          v.rend(),\n",
    "          std::ostream_iterator<int>(std::cout, \" \")); // 40 30 20 10\n",
    "            \n",
    "            \n",
    "// сортировка по возрастанию:\n",
    "std::sort(v.begin(), v.end());\n",
    "        \n",
    "// сортировка по убыванию:\n",
    "std::sort(v.rbegin(), v.rend());\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Конвертация iterator <-> reverse_iterator:\n",
    "\n",
    "Обратите внимание на перескакивание итератора на предыдущий элемент при конвертации."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```c++\n",
    "std::vector<int> v = {10, 20, 30, 40};\n",
    "        \n",
    "auto it = v.begin() + 2; // 30\n",
    "\n",
    "auto rit = std::make_reverse_iterator(it); // 20 !!!!\n",
    "\n",
    "auto it2 = rit.base();  // 30 !!!!\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br />"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Задача: найти последнее число 5 в последовательности, предшествующее первому 10"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Вариант решения:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```c++\n",
    "template<typename It>\n",
    "It function(It begin, It end)\n",
    "{\n",
    "    auto it = std::find(begin, end, 10);\n",
    "    \n",
    "    if (it == end)\n",
    "        return end;  // no 10\n",
    "    \n",
    "    auto rit = std::find(std::make_reverse_iterator(it),\n",
    "                         std::make_reverse_iterator(begin),\n",
    "                         5);\n",
    "\n",
    "    if (rit == std::make_reverse_iterator(begin))\n",
    "        return end;  // no 5 before 10\n",
    "    \n",
    "    return std::next(rit.base());    \n",
    "}\n",
    "\n",
    "std::list<int> l = {1, 2, 3, 5, 5, 10};\n",
    "auto it = function(l.begin(), l.end());\n",
    "auto rit = function(l.rbegin(), l.rend());\n",
    "```"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.8"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
